package algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class MaxQueue {
    private Queue<Integer> elementQueue;
    private Deque<Integer> maxDeque;
//    private int beginIndex;
//    private int endIndex;

    public MaxQueue() {
//        beginIndex = 0;
//        endIndex = 0;
        elementQueue = new LinkedList<Integer>();
        maxDeque = new LinkedList<Integer>();
    }

    public int max_value() {
        return maxDeque.peekFirst() == null ? -1 : maxDeque.peekFirst();
    }

    public void push_back(int value) {
        elementQueue.add(value);
        // 维护一个不递增的队列保存最大值
        while (maxDeque.peekLast() != null && maxDeque.peekLast() < value) maxDeque.pollLast();
        maxDeque.addLast(value);
    }

    public int pop_front() {
        Integer num = elementQueue.poll();
        if (num != null && num.equals(maxDeque.peekFirst())) maxDeque.pollFirst();
        return num == null ? -1 : num;
    }

    public static void main(String[] args) {
        MaxQueue obj = new MaxQueue();
        obj.push_back(46);
        obj.push_back(48);

        obj.push_back(646);
        obj.push_back(229);
        obj.push_back(871);

        int param_3 = obj.pop_front();
        System.out.println(param_3);

        int param_1 = obj.max_value();
        System.out.println(param_1);

        param_3 = obj.pop_front();
        System.out.println(param_3);
        param_1 = obj.max_value();
        System.out.println(param_1);
    }
}
